package com.cube.algorithms.heuristic;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.stream.Collectors;

/**
 * @author litb
 * @since 2025/6/18 16:31
 * <p>
 * 使用遗传算法 (Genetic Algorithm) 解决旅行商问题 (TSP) 的示例。
 * * 该实现包含了解的表示(Tour)、种群(Population)以及核心遗传算法逻辑。
 */

public class TspGeneticAlgorithmExample {

    // --- 1. 基础数据结构 ---

    // --- 3. 主程序入口 ---
    public static void main(String[] args) {
        // 创建城市仓库
        List<City> cities = new ArrayList<>();
        cities.add(new City("北京", 116.46, 39.92));
        cities.add(new City("上海", 121.48, 31.22));
        cities.add(new City("广州", 113.23, 23.16));
        cities.add(new City("深圳", 114.07, 22.62));
        cities.add(new City("成都", 104.06, 30.67));
        cities.add(new City("杭州", 120.19, 30.26));
        cities.add(new City("西安", 108.95, 34.27));
        cities.add(new City("武汉", 114.31, 30.52));
        cities.add(new City("重庆", 106.54, 29.59));
        cities.add(new City("天津", 117.2, 39.13));

        // 初始化遗传算法参数
        GeneticAlgorithm ga = new GeneticAlgorithm(0.015, 5, true);

        // 初始化一个随机种群
        Population population = new Population(50, cities);
        System.out.println("初始最优距离: " + population.getFittest().getTotalDistance());

        // 开始进化，迭代指定的代数
        int generations = 100;
        for (int i = 0; i < generations; i++) {
            population = ga.evolvePopulation(population);
        }

        // 打印最终结果
        Tour bestTour = population.getFittest();
        System.out.println("\n进化 " + generations + " 代后...");
        System.out.println("最终最优距离: " + bestTour.getTotalDistance());
        System.out.println("最终路径: ");
        String pathString = bestTour.getTour().stream()
                .map(City::getName)
                .collect(Collectors.joining(" -> "));
        System.out.println(pathString + " -> " + bestTour.getCity(0).getName());
    }

    /**
     * 城市类，表示地图上的一个点。
     */
    public static class City {
        private final String name;
        private final double x;
        private final double y;

        public City(String name, double x, double y) {
            this.name = name;
            this.x = x;
            this.y = y;
        }

        public String getName() {
            return name;
        }

        public double distanceTo(City other) {
            double deltaX = this.x - other.x;
            double deltaY = this.y - other.y;
            return Math.sqrt(deltaX * deltaX + deltaY * deltaY);
        }

        @Override
        public String toString() {
            return getName();
        }
    }

    /**
     * 路径类 (Tour)，代表一个"个体"或"染色体"。
     * 它封装了一个完整的城市访问序列。
     */
    public static class Tour {
        // 存储路径的基因序列
        private final List<City> tour = new ArrayList<>();
        // 缓存该路径的总距离和适应度，避免重复计算
        private double distance = 0;
        private double fitness = 0;

        /**
         * 创建一个随机的初始个体。
         *
         * @param cities 城市仓库
         */
        public Tour(List<City> cities) {
            List<City> startingTour = new ArrayList<>(cities);
            Collections.shuffle(startingTour);
            this.tour.addAll(startingTour);
        }

        /**
         * 用于创建子代的构造函数。
         *
         * @param tour 初始化的城市列表
         */
        public Tour(ArrayList<City> tour) {
            this.tour.addAll(tour);
        }


        /**
         * 计算并返回该路径的适应度。
         * 适应度越高，代表路径越短（越优）。
         *
         * @return 适应度
         */
        public double getFitness() {
            if (fitness == 0) {
                fitness = 1 / getTotalDistance();
            }
            return fitness;
        }

        /**
         * 计算并返回路径总距离。
         *
         * @return 总距离
         */
        public double getTotalDistance() {
            if (distance == 0) {
                double tourDistance = 0;
                for (int i = 0; i < tour.size(); i++) {
                    City fromCity = getCity(i);
                    City destinationCity;
                    if (i + 1 < tour.size()) {
                        destinationCity = getCity(i + 1);
                    } else {
                        destinationCity = getCity(0);
                    }
                    tourDistance += fromCity.distanceTo(destinationCity);
                }
                this.distance = tourDistance;
            }
            return distance;
        }

        public City getCity(int index) {
            return tour.get(index);
        }

        public void setCity(int index, City city) {
            tour.set(index, city);
            // 路径改变后，清空缓存
            distance = 0;
            fitness = 0;
        }

        public int tourSize() {
            return tour.size();
        }

        public List<City> getTour() {
            return Collections.unmodifiableList(tour);
        }
    }

    // --- 2. 核心遗传算法逻辑 ---

    /**
     * 种群类 (Population)，代表一代所有的个体。
     */
    public static class Population {
        private final List<Tour> tours;

        /**
         * 创建一个种群。
         *
         * @param populationSize 种群大小
         * @param cities         城市仓库
         */
        public Population(int populationSize, List<City> cities) {
            tours = new ArrayList<>(populationSize);
            for (int i = 0; i < populationSize; i++) {
                tours.add(new Tour(cities));
            }
        }

        /**
         * 获取种群中适应度最高的个体。
         *
         * @return 最优路径
         */
        public Tour getFittest() {
            Tour fittest = tours.get(0);
            for (int i = 1; i < tours.size(); i++) {
                if (fittest.getFitness() < tours.get(i).getFitness()) {
                    fittest = tours.get(i);
                }
            }
            return fittest;
        }

        public int populationSize() {
            return tours.size();
        }

        public Tour getTour(int index) {
            return tours.get(index);
        }

        public void saveTour(int index, Tour tour) {
            this.tours.set(index, tour);
        }
    }

    /**
     * 封装了遗传算法的核心操作。
     */
    public static class GeneticAlgorithm {

        private final double mutationRate;
        private final int tournamentSize;
        private final boolean elitism;

        public GeneticAlgorithm(double mutationRate, int tournamentSize, boolean elitism) {
            this.mutationRate = mutationRate;
            this.tournamentSize = tournamentSize;
            this.elitism = elitism;
        }

        /**
         * 进化一个种群，产生下一代。
         *
         * @param pop 当前种群
         * @return 下一代种群
         */
        public Population evolvePopulation(Population pop) {
            Population newPopulation = new Population(pop.populationSize(), new ArrayList<>());

            // 精英主义：如果开启，直接将当前种群的最优个体复制到下一代
            int elitismOffset = 0;
            if (elitism) {
                newPopulation.saveTour(0, pop.getFittest());
                elitismOffset = 1;
            }

            // 循环生成下一代种群的剩余个体
            for (int i = elitismOffset; i < newPopulation.populationSize(); i++) {
                // 选择父代
                Tour parent1 = tournamentSelection(pop);
                Tour parent2 = tournamentSelection(pop);
                // 交叉产生子代
                Tour child = crossover(parent1, parent2);
                // 将子代放入新种群
                newPopulation.saveTour(i, child);
            }

            // 对新种群中的每个个体进行变异
            for (int i = elitismOffset; i < newPopulation.populationSize(); i++) {
                mutate(newPopulation.getTour(i));
            }

            return newPopulation;
        }

        /**
         * 交叉操作 (Ordered Crossover - OX1)。
         * 这是专门为TSP等序列问题设计的交叉方法。
         */
        public Tour crossover(Tour parent1, Tour parent2) {
            // 创建一个空的子代染色体
            ArrayList<City> childTour = new ArrayList<>(Collections.nCopies(parent1.tourSize(), null));

            // 随机选择父代1的一个连续基因片段
            int startPos = (int) (Math.random() * parent1.tourSize());
            int endPos = (int) (Math.random() * parent1.tourSize());

            // 将父代1的基因片段复制到子代
            for (int i = 0; i < childTour.size(); i++) {
                if (i > startPos && i < endPos) {
                    childTour.set(i, parent1.getCity(i));
                } else if (startPos > endPos) {
                    if (!(i < startPos && i > endPos)) {
                        childTour.set(i, parent1.getCity(i));
                    }
                }
            }

            // 遍历父代2，将其余的基因（城市）按顺序填充到子代的空位中
            for (int i = 0; i < parent2.tourSize(); i++) {
                City city = parent2.getCity(i);
                if (!childTour.contains(city)) {
                    for (int ii = 0; ii < childTour.size(); ii++) {
                        if (childTour.get(ii) == null) {
                            childTour.set(ii, city);
                            break;
                        }
                    }
                }
            }
            return new Tour(childTour);
        }

        /**
         * 变异操作 (Swap Mutation)。
         * 随机交换路径中两个城市的位置。
         */
        private void mutate(Tour tour) {
            for (int tourPos1 = 0; tourPos1 < tour.tourSize(); tourPos1++) {
                // 以一个小的概率进行变异
                if (Math.random() < mutationRate) {
                    // 随机选择另一个位置
                    int tourPos2 = (int) (tour.tourSize() * Math.random());

                    // 获取两个位置的城市并交换
                    City city1 = tour.getCity(tourPos1);
                    City city2 = tour.getCity(tourPos2);
                    tour.setCity(tourPos2, city1);
                    tour.setCity(tourPos1, city2);
                }
            }
        }

        /**
         * 选择操作 (Tournament Selection - 锦标赛选择)。
         * 随机选择k个个体，其中最优者胜出。
         */
        private Tour tournamentSelection(Population pop) {
            Population tournament = new Population(tournamentSize, new ArrayList<>());
            // 随机选择k个个体放入锦标赛
            for (int i = 0; i < tournamentSize; i++) {
                int randomId = (int) (Math.random() * pop.populationSize());
                tournament.saveTour(i, pop.getTour(randomId));
            }
            // 返回锦标赛中的最优者
            return tournament.getFittest();
        }
    }
} 